package problem467;

//467.环绕字符串中唯一的子字符串
//https://leetcode.cn/problems/unique-substrings-in-wraparound-string/

class Solution {
    public int findSubstringInWraproundString(String _s) {
        int n = _s.length();
        char[] s = _s.toCharArray();
        int[] dp = new int[n];
        for(int i = 0; i<n; i++) {
            dp[i] = 1;
        }
        //用来去重
        int[] hash = new int[26];
        hash[s[0]-'a'] = 1;
        for(int i = 1; i<n; i++) {
            if(s[i-1]+1 == s[i] || (s[i-1] == 'z' && s[i] == 'a')) {
                dp[i] += dp[i-1];
            }
            hash[s[i]-'a'] = Math.max(hash[s[i]-'a'], dp[i]);
        }
        int sum = 0;
        for(int i = 0; i<26; i++) {
            sum += hash[i];
        }
        return sum;
    }
}

/*
dp[i]:以第i个字符为结尾的子串在base中出现的次数

*/